#define _CRT_SECURE_NO_WARNINGS 1

#include"SeqList.h"

void TestSeqList1()//测试初始化函数，打印函数，尾插尾删
{
	SL sl;//(1) 建立顺序表.
	SeqListInit(&sl);
	SeqListPushBack(&sl, 1);
	SeqListPushBack(&sl, 2);
	SeqListPushBack(&sl, 3);
	SeqListPushBack(&sl, 4);
	SeqListPushBack(&sl, 5);

	SeqListPrint(&sl);

	SeqListPopBack(&sl);
	SeqListPopBack(&sl);
	SeqListPopBack(&sl);
	SeqListPrint(&sl);

	SeqListDestroy(&sl);
}

void TestSeqList2()//测试头插头删
{
	SL sl;
	SeqListInit(&sl);
	SeqListPushBack(&sl, 1);
	SeqListPushBack(&sl, 2);
	SeqListPushBack(&sl, 3);
	SeqListPrint(&sl);

	SeqListPushFront(&sl, 10);
	SeqListPushFront(&sl, 20);
	SeqListPushFront(&sl, 30);
	SeqListPrint(&sl);

	SeqListPopFront(&sl);
	SeqListPopFront(&sl);
	SeqListPrint(&sl);

	SeqListDestroy(&sl);
}

void TestSeqList3()//测试查找函数
{
	SL sl;
	SeqListInit(&sl);
	SeqListPushBack(&sl, 1);
	SeqListPushBack(&sl, 2);
	SeqListPushBack(&sl, 3);
	SeqListPushBack(&sl, 4);
	SeqListPushBack(&sl, 5);
	SeqListPrint(&sl);

	int ret = SeqListFind(&sl, 3);
	if (ret != -1)
	{
		printf("找到了,下标是：%d\n", ret);
	}
	else
	{
		printf("没找到\n");
	}	
	ret = SeqListFind(&sl, 60);
	if (ret != -1)
	{
		printf("找到了,下标是：%d\n", ret);
	}
	else
	{
		printf("没找到\n");
	}
	SeqListDestroy(&sl);
}

void TestSeqList4()//测试指定位置插入删除 返回指定位置元素,返回链表长度
{
	SL sl;
	SeqListInit(&sl);
	SeqListPushBack(&sl, 1);
	SeqListPushBack(&sl, 2);
	SeqListPushBack(&sl, 3);
	SeqListPushBack(&sl, 4);
	SeqListPushBack(&sl, 5);
	SeqListPrint(&sl);

	//SeqListInsert(&sl, 3, 10);
	//SeqListInsert(&sl, 0, 20);//相当于头插
	//SeqListInsert(&sl, 6, 30);
	//SeqListInsert(&sl, 8, 40);//相当于尾插
    //SeqListPrint(&sl);

	SeqListErase(&sl, 3);
	SeqListErase(&sl, 0);//相当于头删
	SeqListPrint(&sl);

	SeqListErase(&sl, 2);//相当于尾删
	SeqListPrint(&sl);

	printf("长度：%d\n", SeqListLength(&sl));
	printf("%d\n", SeqListPos(&sl, 1));

	SeqListDestroy(&sl);
}

void TestSeqList5()//测试新的尾插尾删，头插头删
{
	//SL sl;
	//SeqListInit(&sl);
	//SeqListPushBack(&sl, 1);
	//SeqListPushBack(&sl, 2);
	//SeqListPushBack(&sl, 3);
	//SeqListPushBack(&sl, 4);
	//SeqListPushBack(&sl, 5);
	//SeqListPrint(&sl);

	//SeqListPopBack(&sl);
	//SeqListPopBack(&sl);
	//SeqListPopBack(&sl);
	//SeqListPrint(&sl);

	SL sl;
	SeqListInit(&sl);
	SeqListPushBack(&sl, 1);
	SeqListPushBack(&sl, 2);
	SeqListPushBack(&sl, 3);
	SeqListPrint(&sl);

	SeqListPushFront(&sl, 10);
	SeqListPushFront(&sl, 20);
	SeqListPushFront(&sl, 30);
	SeqListPrint(&sl);

	SeqListPopFront(&sl);
	SeqListPopFront(&sl);
	SeqListPrint(&sl);

	SeqListDestroy(&sl);
}

void menu() 
{
	printf("\n");
	printf("########################\n");
	printf("#  1. 头插    2. 头删  #\n");
	printf("#  3. 尾插    4. 尾删  #\n");
	printf("#  5. 打印    6. 查找  #\n");
	printf("#  7. 指定位置插入     #\n");
	printf("#  8. 指定位置删除     #\n");
	printf("#  0. 退出程序         #\n");
	printf("########################\n");
}

enum SQ 
{
	CLOSE,      //0  把CLOSE放在第一个，正好顺势推下去
	PUSH_FRONT, //1
	POP_FRONT,  //2
	PUSH_BACK,  //3
	POP_BACK,   //4
	PRINT,      //5
	SEARCH,     //6
	INSERT,     //7
	EARSE,      //8
};

void TestMenu()
{
	SL sl;
	SeqListInit(&sl);
	int input = 0, x = 0, pos = 0;
	do 
	{
		menu();
		printf("请选择操作: ");
		scanf("%d", &input);
		switch (input) 
		{
		case CLOSE: //退出（0）
			printf("已退出\n");
			break;
		case PUSH_FRONT: //头插（1）
			printf("请输入你要头插的数据，以-1结束: ");
			scanf("%d", &x);
			while (x != -1) 
			{
				SeqListPushFront(&sl, x);
				scanf("%d", &x);
			}
			break;
		case POP_FRONT: //头删（2）
			SeqListPopFront(&sl);
			printf("已删除\n");
			break;

		case PUSH_BACK: //尾插（3）
			printf("请输入你要尾插的数据，以-1结束: ");
			scanf("%d", &x);
			while (x != -1) 
			{
				SeqListPushBack(&sl, x);
				scanf("%d", &x);
			}
			break;
		case POP_BACK: //尾删（4）
			SeqListPopBack(&sl);
			printf("已删除\n");
			break;
		case PRINT: //打印（5）
			printf("顺序表：");
			SeqListPrint(&sl);
			break;
		case SEARCH: //查找（6）
			printf("请输入查找的数据: ");
			scanf("%d", &x);
			int ret = SeqListFind(&sl, x);
			if (ret != -1) 
			{
				printf("找到了，下标为 %d\n", ret);
			}
			else 
			{
				printf("找不到\n");
			}
			break;
		case INSERT: //指定位置插入 (7)
			printf("请输入你要插入的位置的下标: ");
			scanf("%d", &pos);
			printf("请输入你要插入的数据，以-1结束: ");
			scanf("%d", &x);
			while (x != -1) 
			{
				SeqListInsert(&sl, pos, x);
				scanf("%d", &x);
			}
			break;
		case EARSE: //指定位置删除 (8)
			printf("请输入你要删除的位置的下标: ");
			scanf("%d", &pos);
			SeqListErase(&sl, pos);
			printf("已删除\n");
			break;
		default:
			printf("输入错误，请重新输入！\n");
			break;
		}
	} while (input);
	SeqListDestroy(&sl); //销毁
}

void TestSeqListMerge()
{
	SL sla;
	SeqListInit(&sla);
	SeqListPushBack(&sla, 1);
	SeqListPushBack(&sla, 3);
	SeqListPushBack(&sla, 6);
	SeqListPushBack(&sla, 8);
	SeqListPushBack(&sla, 9);
	printf("a顺序表：\n");
	SeqListPrint(&sla);

	SL slb;
	SeqListInit(&slb);
	SeqListPushBack(&slb, 2);
	SeqListPushBack(&slb, 3);
	SeqListPushBack(&slb, 4);
	SeqListPushBack(&slb, 5);
	SeqListPushBack(&slb, 5);
	SeqListPushBack(&slb, 6);
	SeqListPushBack(&slb, 7);
	printf("b顺序表：\n");
	SeqListPrint(&slb);

	printf("合并后：\n");
	SL slc = SeqListMerge(&sla, &slb);
	printf("c顺序表：\n");
	SeqListPrint(&slc);
	printf("a顺序表：\n");
	SeqListPrint(&sla);
	printf("b顺序表：\n");
	SeqListPrint(&slb);

	SeqListDestroy(&sla);
	SeqListDestroy(&slb);
	SeqListDestroy(&slc);
}

int main()
{
	//TestSeqList1();//测试初始化函数，打印函数，尾插尾删
	//TestSeqList2();//测试头插头删
	//TestSeqList3();//测试查找函数
	//TestSeqList4();//测试指定位置插入删除  返回指定位置元素,返回链表长度
	//TestSeqList5();//测试新的尾插尾删，头插头删
	//TestMenu();//测试菜单和整个程序
	TestSeqListMerge();//测试顺序表合并

	return 0;
}

//989. 数组形式的整数加法
//整数的 数组形式  num 是按照从左到右的顺序表示其数字的数组。
//
//例如，对于 num = 1321 ，数组形式是[1, 3, 2, 1] 。
//给定 num ，整数的 数组形式 ，和整数 k ，返回 整数 num + k 的 数组形式 。
//示例 1：
//
//输入：num = [1, 2, 0, 0], k = 34
//输出：[1, 2, 3, 4]
//解释：1200 + 34 = 1234
//示例 2：
//
//输入：num = [2, 7, 4], k = 181
//输出：[4, 5, 5]
//解释：274 + 181 = 455
//示例 3：
//
//输入：num = [2, 1, 5], k = 806
//输出：[1, 0, 2, 1]
//解释：215 + 806 = 1021
//
//
//提示：
//
//1 <= num.length <= 10^4
//0 <= num[i] <= 9
//num 不包含任何前导零，除了零本身
//1 <= k <= 10^4

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
//void reverse(int* p, int sz)
//{
//	int left = 0, right = sz - 1;
//	while (left < right)
//	{
//		int tmp = p[left];
//		p[left] = p[right];
//		p[right] = tmp;
//		left++;
//		right--;
//	}
//}
//int* addToArrayForm(int* num, int numSize, int k, int* returnSize) {
//	int count = 0;
//	int tmp = k;
//	while (tmp)
//	{
//		tmp /= 10;
//		count++;
//	}
//
//	int max = (count + 1) > (numSize + 1) ? (count + 1) : (numSize + 1);
//	int* ptr = (int*)calloc(max, sizeof(int));
//	int* p = ptr;
//	int* ret = ptr;
//
//	count = 0;
//	int j = 0, i = numSize - 1;
//	for (;i >= 0;i--, j++)
//	{
//		ptr[j] = num[i] + (k % 10) + ptr[j];
//		k /= 10;
//		if (ptr[j] >= 10)
//		{
//			ptr[j + 1] += ptr[j] / 10;
//			ptr[j] %= 10;
//		}
//		count++;
//	}
//	while (i == 0 && k != 0)
//	{
//		ptr[j] += (k % 10) + ptr[j];
//		if (ptr[j - 1] >= 10)
//		{
//			ptr[j] += ptr[j - 1] / 10;
//			ptr[j - 1] %= 10;
//		}
//		count++;
//		j++;
//		k /= 10;
//	}
//	if (p[count] == 0)
//	{
//		reverse(p, count);
//		*returnSize = count;
//	}
//	else
//	{
//		reverse(p, count + 1);
//		*returnSize = count + 1;
//	}
//	return ret;
//}
//
//void reverse(int* p, int sz)
//{
//	int left = 0, right = sz - 1;
//	while (left < right)
//	{
//		int tmp = p[left];
//		p[left] = p[right];
//		p[right] = tmp;
//		left++;
//		right--;
//	}
//}
//int* addToArrayForm(int* num, int numSize, int k, int* returnSize) {
//
//	int count = 0;
//	int tmp = k;
//	while (tmp)
//	{
//		tmp /= 10;
//		count++;
//	}
//	int max = (count + 1) > (numSize + 1) ? (count + 1) : (numSize + 1);
//	int* res = (int*)calloc(max, sizeof(int));
//
//	*returnSize = 0;
//	for (int i = numSize - 1; i >= 0 || k > 0; i--)
//	{
//		if (i >= 0)
//		{
//			k += num[i];//把原数组的右边的元素依次加到K中
//		}
//		res[(*returnSize)++] = k % 10;//把k的低位放到数组新数组左边，后面逆置就行
//		k /= 10;
//	}
//	reverse(res, *returnSize);
//	return res;
//}